//线索二叉树的实现
/*
  先序线索化时较为特殊，需要当心死循环(加一个指针类型判断)
*/

#include "BiTNode.h"
#include <iostream>

using namespace std;

BiTNode *pre = nullptr; //全局变量用于指向前一个结点

void visit(BiTNode *N) //线索化的访问操作
{
    // cout << N->data;
    if (N != nullptr && N->lchild == nullptr) //若左指针域为空，则线索化
    {
        N->ltag = 1;     //标志位赋值为1，表示该指针为线索
        N->lchild = pre; //线索指向前一个结点
    }
    if (pre != nullptr && pre->rchild == nullptr) //若前一个结点的右指针域为空，则线索化
    {
        pre->rtag = 1;   //标志位赋值为1
        pre->rchild = N; //线索指向后一个结点
    }
    pre = N;
    return;
}

void InThread(BiTree T) //中序线索化(左根右)
{
    if (T != nullptr) //若T不为空树，则递归中序遍历
    {
        InThread(T->lchild);
        visit(T); //访问操作
        InThread(T->rchild);
    }
    return;
}

void PreThread(BiTree T) //先序线索化(根左右)
{
    if (T != nullptr) //若T不为空树，则递归先序遍历
    {
        visit(T);
        if (T->ltag == 0) //这里的判断非常重要，不可省去！！否则会陷入死循环，而且这个判断不可以添加在后序线索化中，否则会出问题！
            PreThread(T->lchild);
        PreThread(T->rchild);
    }
    return;
}

void PostThread(BiTree T) //后序线索化(左右根)
{
    if (T != nullptr) //若T不为空树，则递归后序遍历
    {
        PostThread(T->lchild);
        PostThread(T->rchild);
        visit(T);
    }
    return;
}

int main()
{
    //初始化为ExampleTree1
    BiTree T = (BiTNode *)malloc(sizeof(BiTNode));
    InitT1(T);

    //测试代码
    // InThread(T);

    PreThread(T);

    // PostThread(T);
    if (pre->rchild == nullptr) //使线索二叉树遍历序列的最后一个结点的右指针域线索化(tag = 1)
        pre->rtag = 1;
    cout << T->lchild->lchild->lchild->data;
    return 0;
}